package com.renyq.algorithm.doublePointer

/**
 *题目：输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？假设数组中存在且只存在一对符合条件的数字，
 *      同时一个数字不能使用两次。例如，输入数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标分别为1与3。
 *
 * @author renyongqiang
 * @since 2021/10/17
 */
class TwoNumberSum {
    /**
     * 利用HashMap来查找
     */
    fun getIndex(arrays: IntArray, targetNumber: Int): IntArray {
        val map = HashMap<Int, Int>()
        for ((index, value) in arrays.withIndex()) {
            map[value] = index
        }
        for ((index, value) in arrays.withIndex()) {
            val otherNumber = targetNumber - value
            if (map.containsKey(otherNumber)) {
                val otherIndex = map[otherNumber]
                return intArrayOf(index, otherIndex!!)
            }
        }
        return intArrayOf()
    }

    /**
     * 利用双指针查找
     */
    fun getIndex2(arrays: IntArray, targetNumber: Int): IntArray {
        if (arrays.size <= 2) {
            return if (arrays.size == 2 && arrays[0] + arrays[1] == targetNumber) intArrayOf(0, 1) else intArrayOf()
        }
        var left = 0
        var right = arrays.size - 1
        while (left < right) {
            when {
                arrays[left] + arrays[right] == targetNumber -> return intArrayOf(left, right)
                arrays[left] + arrays[right] > targetNumber -> right--
                else -> left++
            };
        }
        return intArrayOf()
    }
}

fun main() {
    val arrays = intArrayOf(1, 2, 4, 6, 10)
    val targetNumber = 8
    val twoNumberSum = TwoNumberSum()
    val intArray = twoNumberSum.getIndex2(arrays, targetNumber)
    for (value in intArray) {
        print(" $value")
    }
}